package com.company.algo.listnode;

import com.company.algo.pojo.ListNode;

/**https://www.bilibili.com/video/BV1HA411q7tH?from=search&seid=8127053556998590280
 * 【用快速排序来排单向链表】

 * 【使用归并排序排单向链表】https://leetcode-cn.com/problems/sort-list/solution/sort-list-gui-bing-pai-xu-lian-biao-by-jyd/
 */
public class SortListNode {
    public ListNode sortList(ListNode head) {
        if (head == null||head.next == null) return head;
        //通过快慢指针找到链表的中点
        ListNode slow = head, fast = head.next;
        while (fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //划分
        ListNode anotherHead = slow.next;
        slow.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(anotherHead);
        //归并
        ListNode dummy = new ListNode(0);
        ListNode h = dummy;
        while (left!=null && right!=null){
            if (left.val < right.val){
                h.next = left;
                left = left.next;
            }else {
                h.next = right;
                right = right.next;
            }
            h = h.next;
        }
        h.next = left != null ? left: right;
        return dummy.next;
    }


}
